package datastructure.array;

/**
 * Find the continuous interval [a, b] in Array A, so that sum (A[a] + ... + A[b])
 * is maximal
 * 
 * @author Lei
 */
public class FindMaximalSubarraySum {

    // the sum is negative, regard the maximal as zero
    public static int findMaximalSubarraySum(int A[]) {
        int maxSoFar = 0;
        int maxEndingSoFax = 0;

        for (int i = 0; i < A.length; i++) {
            maxEndingSoFax = Math.max(maxEndingSoFax + A[i], 0);
            maxSoFar = Math.max(maxSoFar, maxEndingSoFax);
        }
        return maxSoFar;
    }

    public static void main(String args[]) {

        int[] anArray = {
            -1,
            -2,
            -5,
            -4,
            -5,
            -6
        };

        System.out.println(FindMaximalSubarraySum.findMaximalSubarraySum(anArray));
    }
}
